package practice_2025_9.practice_9_23;

import java.util.*;

class Solution {
    /**
     * 最长重复子串
     * @param s
     * @return
     */
    public String longestDupSubstring(String s) {
        // s 的最长重复子串, 在 s 中出现 2 次或更多次(出现次数可能存在重叠)
        // 长度为 n, 最长重复长度 n-1 -> 依次寻找是否可能存在重复子串
        // 可能重复长度 [0, n - 1] -> 二分
        int len = s.length();
        int left = 0, right = len - 1;
        String res = "";
        while(left <= right) {
            // 要寻找的重复长度 [0, mid)
            int mid = (left + right + 1) / 2;
            String str = find(s, mid);
            if (str.equals("")) {
                // 没找到
                right = mid - 1;
            } else {
                // 找到了
                left = mid + 1;
                res = str;
                System.out.println("mid: " + mid + " res: " + res);
            }
        }
        return res;
    }
    // 找到相同的字符串 [0, end)
    // s 由小写字母组成
    // 有哈希冲突的可能
    long PRIME = 131;
    public String find(String s, int end) {
        Set<Long> set = new HashSet<>();
        long hash = 0;
        long p = 1;
        for(int i = 0; i < end; i++) {
            hash = hash * PRIME + s.charAt(i);
            p *= PRIME;
        }
        set.add(hash);
        for(int i = end; i < s.length(); i++) {
            // String tmp = s.substring(i, i + end);
            // 计算当前的 hash 值
            hash = hash * PRIME + s.charAt(i) - p * s.charAt(i - end);
            if (set.contains(hash)) {
                return s.substring(i - end + 1, i + 1);
            } else {
                set.add(hash);
            }
        }
        return "";
    }

    /**
     * 全排列II
     */
    List<Integer> list = new ArrayList<>();
    List<List<Integer>> res = new ArrayList<>();
    boolean[] vis;
    public List<List<Integer>> permuteUnique(int[] nums) {
        int len = nums.length;
        vis = new boolean[len];
        Arrays.sort(nums);
        permute(nums);
        return res;
    }
    public void permute(int[] nums) {
        int len = nums.length;
        // 递归出口
        if (list.size() >= len) {
            res.add(new ArrayList(list));
            return;
        }
        for(int i = 0; i < len; i++) {
            if (!vis[i] && (i == 0 || nums[i] != nums[i - 1] || vis[i - 1])) {
                vis[i] = true;
                list.add(nums[i]);
                permute(nums);
                vis[i] = false;
                list.remove(list.size() - 1);
            }
        }
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        System.out.println(solution.longestDupSubstring("xnahfslefuigqaaaaaaaaaaaaa"));
    }
}